package mo.leetcode_top;

public class LI1714_02 {

    public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[k];
        }
        int left = 0;
        int right = arr.length - 1;
        int target = k - 1;
        while (true) {
            int pivot = partition(arr, left, right);
            if (pivot == target) {
                break;
            } else if (pivot < target) {
                left = pivot + 1;
            } else {
                right = pivot - 1;
            }
        }
        int[] res = new int[k];
        System.arraycopy(arr, 0, res, 0, k);
        return res;
    }

    private int partition(int[] arr, int left, int right) {
        int counter = left;
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[right]) {
                swap(arr, i, counter);
                counter++;
            }
        }
        swap(arr, counter, right);
        return counter;
    }


    private void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
